//<p>给定整数数组 <code>nums</code> 和整数 <code>k</code>，请返回数组中第 <code><strong>k</strong></code> 个最大的元素。</p>
//
//<p>请注意，你需要找的是数组排序后的第 <code>k</code> 个最大的元素，而不是第 <code>k</code> 个不同的元素。</p>
//
//<p>你必须设计并实现时间复杂度为 <code>O(n)</code> 的算法解决此问题。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1:</strong></p>
//
//<pre>
//<strong>输入:</strong> <span><code>[3,2,1,5,6,4],</code></span> k = 2
//<strong>输出:</strong> 5
//</pre>
//
//<p><strong>示例&nbsp;2:</strong></p>
//
//<pre>
//<strong>输入:</strong> <span><code>[3,2,3,1,2,4,5,5,6], </code></span>k = 4
//<strong>输出:</strong> 4</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示： </strong></p>
//
//<ul> 
// <li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li> 
// <li><code>-10<sup>4</sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>4</sup></code></li> 
//</ul>
//
//<div><div>Related Topics</div><div><li>数组</li><li>分治</li><li>快速选择</li><li>排序</li><li>堆（优先队列）</li></div></div><br><div><li>👍 1815</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 数组中的第K个最大元素
 * @author DY Rising
 * @date 2022-08-16 19:57:12
 */
public class P215_KthLargestElementInAnArray{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P215_KthLargestElementInAnArray().new Solution();
        System.out.println(solution.findKthLargest(new int[]{3,2,1,5,6,4}, 3));
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

    public class Solution {

        public int findKthLargest(int[] nums, int k) {
            int len = nums.length;
            // 使用一个含有 k 个元素的最小堆，PriorityQueue 底层是动态数组，为了防止数组扩容产生消耗，可以先指定数组的长度
            //PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, Comparator.comparingInt(a -> a));
            PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
            // Java 里没有 heapify ，因此我们逐个将前 k 个元素添加到 minHeap 里
            for (int i = 0; i < k; i++) {
                minHeap.offer(nums[i]);
            }

            for (int i = k; i < len; i++) {
                // 看一眼，不拿出，因为有可能没有必要替换
                Integer topElement = minHeap.peek();
                // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
                if (nums[i] > topElement) {
                    // Java 没有 replace()，所以得先 poll() 出来，然后再放回去
                    minHeap.poll();
                    minHeap.offer(nums[i]);
                }
            }
            return minHeap.peek();
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}
